package _06_动态规划;

public class _152_乘积最大子数组 {

    public int maxProduct(int[] nums) {
        int min = nums[0];
        int max = nums[0];
        int result = max;
        for (int i = 1; i < nums.length; i++) {
            int tempMax = max;
            max = Math.max(nums[i], Math.max(nums[i] * max, nums[i] * min));
            min = Math.min(nums[i], Math.min(nums[i] * tempMax, nums[i] * min));
            result = Math.max(result, max);
        }
        return result;
    }

    public int maxProduct3(int[] nums) {
        // 正向查找，找到最大序列，遇到0，乘积为1
        int max = nums[0];
        int sum = 1;
        for (int num : nums) {
            sum *= num;
            if (max < sum) max = sum;
            if (num == 0) sum = 1;
        }

        sum = 1;
        // 方向查找。再次寻找最大值
        for (int i = nums.length - 1; i >= 0; i--) {
            sum *= nums[i];
            if (max < sum) max = sum;
            if (nums[i] == 0) sum = 1;
        }
        return max;
    }

    // 动态规划优化
    public int maxProduct2(int[] nums) {
        int len = nums.length;
        int maxF = nums[0];
        int minF = nums[0];
        int max = maxF;
        for (int i = 1; i < len; i++) {
            int tempMax = maxF;
            maxF = Math.max(maxF * nums[i], Math.max(nums[i], nums[i] * minF));
            minF = Math.min(minF * nums[i], Math.min(nums[i], nums[i] * tempMax));
            max = Math.max(max, maxF);
        }
        return max;
    }

    // 记录最大，最小连续子序列乘积
    public int maxProduct1(int[] nums) {
        int[] maxF = new int[nums.length];
        int[] minF = new int[nums.length];
        maxF[0] = nums[0];
        minF[0] = nums[0];
        int max = maxF[0];
        for (int i = 1; i < nums.length; i++) {
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], nums[i] * minF[i - 1]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], nums[i] * maxF[i - 1]));
            max = Math.max(max, maxF[i]);
        }
        return max;
    }

}
